<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <!-- 四数之和 -->
    <script>
      var fourSum = function (nums, target) {
        let res = []
        nums = nums.sort((a, b) => a - b) // 关键的排序
        let len = nums.length
        let dfs = (ix, target, slen, path = []) => {
          if (slen === 0) {
            if (target === 0) {
              res.push([...path])
            }
            return
          }
          for (let j = ix; j <= len - slen && slen * nums[j] <= target; ++j) {
            if (
              (j > ix && nums[j] == nums[j - 1]) ||
              nums[j] + (slen - 1) * nums[len - 1] < target // 1. 当前和其前一个相同，剪枝 2.当前值加上最大值填充的余下坑位，如果还是小于target，剪枝。
            ) {
              //剪枝 保证不重复
              continue
            }
            path.push(nums[j])
            dfs(j + 1, target - nums[j], slen - 1, path)
            path.pop()
          }
        }
        dfs(0, target, 4)
        return res
      }
      console.log(fourSum([1, 0, -1, 0, -2, 2], 0))
    </script>
  </body>
</html>
